home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / awe / awe-full.lha / Awe2 / DoNotUseThisSrc / SharedMalloc-bogus.cc < prev    next >
C/C++ Source or Header  |  1990-08-08  |  10KB  |  414 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. // 
  3. // Copyright (C) 1988 University of Illinois, Urbana, Illinois
  4. //
  5. // written by Dirk Grunwald (grunwald@cs.uiuc.edu)
  6. //
  7. //
  8. // Allocator.c: based loosely on...
  9. //
  10. // malloc.c (Caltech) 2/21/82
  11. // Chris Kingsley, kingsley@cit-20.
  12. //
  13. //    $Header: /foobar/grunwald/Awe2/NewSrc/RCS/SharedMalloc-bogus.cc,v 4.1 89/10/18 13:28:18 grunwald Exp Locker: grunwald $
  14. //
  15. // This is a very fast storage allocator.  It allocates blocks of a small 
  16. // number of different sizes, and keeps free lists of each size. In this 
  17. // implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  18. // 
  19.  
  20. #define NDEBUG
  21.  
  22. #define DEBUG
  23.  
  24.  
  25. #ifdef __GNUG__
  26. #  pragma implementation
  27. #endif
  28.  
  29. #include <stdio.h>
  30. #include <stream.h>
  31. #include "Debug.h"
  32. #include "assert.h"
  33. #include "CpuMultiplexor.h"
  34.  
  35. #ifdef __GNUG__
  36. extern "C" {
  37. #endif
  38.  
  39. void *sbrk(int);
  40. void exit(int x = 0);
  41. void *malloc( unsigned );
  42. void free(void *);
  43. void perror(const char*);
  44.  
  45. #ifdef __GNUG__
  46. };
  47. #endif
  48.  
  49. const int NOTREACHED = 0;
  50.  
  51. extern int CpuMuxDebugFlag;
  52.  
  53. //
  54. //    calloc and cfree are defined in terms of malloc.
  55. //    alloca allocates space from the current stack.
  56. //
  57.  
  58. #include "assert.h"
  59. #include "SpinLock.h"
  60.  
  61. //
  62. // Allocator.h: based loosely on...
  63. //
  64. // malloc.c (Caltech) 2/21/82
  65. // Chris Kingsley, kingsley@cit-20.
  66. //
  67. //    $Header: /foobar/grunwald/Awe2/NewSrc/RCS/SharedMalloc-bogus.cc,v 4.1 89/10/18 13:28:18 grunwald Exp Locker: grunwald $
  68. //
  69. // 
  70.  
  71. //
  72. // Below is a allocator sbuclass based loosely on..
  73. //
  74. // malloc.c (Caltech) 2/21/82
  75. // Chris Kingsley, kingsley@cit-20.
  76. //
  77. // This is a very fast storage allocator.  It allocates blocks of a small 
  78. // number of different sizes, and keeps free lists of each size. In this 
  79. // implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  80. // 
  81.  
  82. //
  83. // The overhead on a block is at least 4 bytes.  When free, this space
  84. // contains a pointer to the next free block, and the bottom two bits must
  85. // be zero.  When in use, the first byte is set to MAGIC, and the second
  86. // byte is the size index.  The remaining bytes are for alignment.
  87. // If range checking is enabled and the size of the block fits
  88. // in two bytes, then the top two bytes hold the size of the requested block
  89. // plus the range checking words, and the header word MINUS ONE.
  90. // 
  91. union    overhead {
  92.     union    overhead * ov_next;    // when free
  93.     struct {
  94.     unsigned char    ovu_magic;    // magic number
  95.     unsigned char    ovu_index;    // bucket #
  96.     unsigned short    ovu_size;    // actual block size
  97.     unsigned int    ovu_rmagic;    // range magic number
  98.     } ovu;
  99. };
  100.  
  101. #define    ov_magic    ovu.ovu_magic
  102. #define    ov_index    ovu.ovu_index
  103. #define    ov_size        ovu.ovu_size
  104. #define    ov_rmagic    ovu.ovu_rmagic
  105.  
  106. #define    MAGIC        0xff        /* magic # on accounting info */
  107. #define RMAGIC        0x55555555    /* magic # on range info */
  108. #define    RSLOP        sizeof( unsigned int )
  109.  
  110. //
  111. // nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  112. // smallest allocatable block is 8 bytes.  The overhead information
  113. // precedes the data area returned to the user.
  114. // 
  115.  
  116. int const NumberOfBuckets = 30;
  117.  
  118. class BucketAllocator {
  119. protected:
  120.     union overhead * nextf[ NumberOfBuckets ];
  121.     SpinLock bucketLock[ NumberOfBuckets ];
  122.     
  123.     SpinLock topLock;
  124.     char * top;
  125.  
  126.     char sbrkDisabled;
  127.     char initialized;
  128.     
  129.     int morecore( int bucket );
  130.  
  131.     void initialize();
  132. public:
  133.     BucketAllocator();
  134.     ~BucketAllocator();
  135.     void * allocate( unsigned nbytes );
  136.     void free( void * cp );
  137.     void disableFurtherBreaks();
  138. };
  139.  
  140. BucketAllocator HardwareMemoryAllocator;
  141.  
  142. BucketAllocator::BucketAllocator()
  143. {
  144.     initialize();
  145. }
  146.  
  147. void
  148. BucketAllocator::disableFurtherBreaks()
  149. {
  150.     sbrkDisabled = 1;
  151. }
  152.  
  153. void disableFurtherBreaks()
  154. {
  155.     HardwareMemoryAllocator.disableFurtherBreaks();
  156. }
  157.  
  158. void
  159. BucketAllocator::initialize()
  160. {
  161.     if (initialized) return;
  162.     //
  163.     // First allocate the state information for the object from the
  164.     // sourceMemoryObjectCache.
  165.     // 
  166.  
  167.     for( int i = 0; i < NumberOfBuckets; i++ ) {
  168.     nextf[ i ] = 0;
  169.     }
  170.     
  171.     extern int end;
  172.     top = (char *) &end;
  173.     sbrkDisabled = 0;
  174.     initialized = 1;
  175. }
  176.  
  177. //
  178. //    Deleteing the allocator doesn't free up your memory, it just
  179. //    makes us forget about it. However, this is only done when
  180. //    you call exit, so who cares.
  181. //
  182. BucketAllocator::~BucketAllocator()
  183. {
  184. }
  185.  
  186. void *
  187. BucketAllocator::allocate( unsigned nbytes )
  188. {
  189.     if (!initialized) {
  190.     initialize();
  191.     }
  192.  
  193.     union overhead * p;
  194.     int bucket = 0;
  195.     unsigned shiftr;
  196.  
  197. #ifndef NDEBUG    
  198.     if (CpuMuxDebugFlag) {
  199.     cerr << "BucketAllocator::allocate( " << nbytes;
  200.     cerr << " ) for top = " << hex(long(top)) << "\n";
  201.     }
  202. #endif
  203.     //
  204.     // Convert amount of memory requested into
  205.     // closest block size stored in hash buckets
  206.     // which satisfies request.  Account for
  207.     // space used per block for accounting.
  208.     // 
  209.     nbytes += sizeof( union overhead ) + RSLOP;
  210.     nbytes = ( nbytes + 3 ) &~ 3; 
  211.     shiftr = ( nbytes - 1 ) >> 2;
  212.     // apart from this loop, this is O(1) */
  213.      while( shiftr >>= 1 )
  214.      bucket++;
  215.     
  216.     Debug( "BucketAllocator::allocate: nbytes=%x, shiftr=%x, bucket=%x\n",
  217.       nbytes, shiftr, bucket );
  218.     assert( bucket < NumberOfBuckets );
  219.     
  220.     //
  221.     // If nothing in hash bucket right now, request more memory from
  222.     // the system.
  223.     // This is probably pathalogical (?) and can lead to one processor
  224.     // always allocation memory for everybody else, but hopefully the
  225.     // locks will make it somewhat fairer.
  226.     // 
  227.     Debug( "BucketAllocator::allocate: waiting on bucket %d lock\n",
  228.       bucket );
  229.     bucketLock[bucket].reserve();
  230.     while( nextf[ bucket ] == 0 ) {
  231.     Debug( "BucketAllocator::allocate: filling bucket %d\n",
  232.           bucket );
  233.     bucketLock[bucket].release();
  234.     if( ! morecore( bucket ) )
  235.         break;
  236.     bucketLock[bucket].reserve();
  237.     }
  238.     Debug( "BucketAllocator::allocate: nextf[bucket] = %x\n",
  239.       nextf[bucket] );
  240.     if( nextf[bucket] == 0 ) {
  241.     fprintf(stderr, "BucketAllocator::allocate REALLY out of memory\n" );
  242.     bucketLock[bucket].release();
  243.     return( 0 );
  244.     }
  245.     
  246.     //
  247.     // Grab the next entry in the bucket.
  248.     // 
  249.     p = nextf[ bucket ];
  250.     Debug( "BucketAllocator::allocate: p = %x\n", p );
  251.     
  252.     //
  253.     // remove from linked list
  254.     // 
  255.     nextf[ bucket ] = nextf[ bucket ]->ov_next;
  256.     bucketLock[bucket].release();
  257.     
  258.     p->ov_magic = MAGIC;
  259.     p->ov_index= bucket;
  260.     
  261.     //
  262.     // Record allocated size of block and
  263.     // bound space with magic numbers.
  264.     // 
  265.     if( nbytes <= 0x10000 )
  266.     p->ov_size = nbytes - 1;
  267.     p->ov_rmagic = RMAGIC;
  268.     *((unsigned int *) ((char *) p + nbytes - RSLOP)) = RMAGIC;
  269.     
  270.     Debug( "BucketAllocator::allocate: returning %A\n", (char *) (p + 1) );
  271.     return((void*) ((char *) (p + 1)) );
  272. }
  273.  
  274. //
  275. // Get more memory into a bucket. Also prefetch the memory.
  276. // 
  277. int
  278. BucketAllocator::morecore( int bucket )
  279. {
  280.     union overhead * op;
  281.     int rnu;       // 2^rnu bytes will be requested
  282.     int nblks;     // become nblks blocks of the desired size
  283.     int siz;
  284.     
  285.     Debug( "BucketAllocator::morecore( bucket:%d )\n", bucket );
  286.     
  287.     //
  288.     // take PAGESIZE (4k) unless the block is bigger than that
  289.     //
  290.     
  291.     rnu = ( bucket <= 9 ) ? 12 : bucket + 3;
  292.     nblks = 1 << ( rnu - ( bucket + 3 ) );  // how many blocks to get
  293.     if( rnu < bucket )
  294.     rnu = bucket;
  295.     
  296.     Debug( "BucketAllocator::morecore(): getting %d bytes\n", 1 << rnu );
  297.     
  298.     //
  299.     // See if there is room left in the cached space for the request.
  300.     // 
  301.     topLock.reserve();
  302.     int nbytes = 1 << rnu;
  303.     
  304.     char *highest = (char *) sbrk(0);
  305.     
  306.     if ( ( top + nbytes ) > highest ) {
  307.     if ( sbrkDisabled ) {
  308.  
  309.         cerr << "BucketAllocator::morecore: out of memory\n";
  310.         cerr << "top     = " << hex(long(top)) << "\n";
  311.         cerr << "highest = " << hex(long(highest)) << "\n";
  312.         cerr << "sbrk(0) = " << hex(long(sbrk(0))) << "\n";
  313.  
  314.         topLock.release();
  315.  
  316.         return( 0 );
  317.     }
  318.     else {
  319.         //
  320.         //    Get more space & reduce the number of system calls.
  321.         //
  322.         highest = (char *) sbrk(nbytes * 2);
  323.     }
  324.     }
  325.     
  326.     op = (union overhead *) top;
  327.     top += nbytes;
  328.     topLock.release();
  329.     //
  330.     // Round up to minimum allocation size boundary
  331.     // and deduct from block count to reflect.
  332.     // 
  333.     if( (int) op & 7 ) {
  334.     op = (union overhead *) (((int)op + 8) &~ 7);
  335.     nblks--;
  336.     }
  337.     Debug( "BucketAllocator::morecore(): adjusted op = %x\n", op );
  338.     
  339.     //
  340.     // Add new memory allocated to that on
  341.     // free list for this hash bucket.
  342.     // 
  343.     siz = 1 << ( bucket + 3 );
  344.     
  345.     union overhead * block = op;
  346.     
  347.     Debug( "BucketAllocator::morecore(): nblks = %d  size = %d\n",
  348.       nblks, siz );
  349.     while( --nblks > 0 ) {
  350.     block->ov_next = (union overhead *) ( (char *) block + siz );
  351.     block = (union overhead *) ( (char *) block + siz );
  352.     }
  353.     Debug( "BucketAllocator::morecore(): adding new memory to bucket %d\n",
  354.       bucket );
  355.     
  356.     bucketLock[bucket].reserve();
  357.     
  358.     block->ov_next = nextf[ bucket ];    // terminate the list with
  359.     // anything that was already 
  360.     // there..
  361.     nextf[ bucket ] = op;
  362.     
  363.     bucketLock[bucket].release();
  364.     return( 1 );
  365. }
  366.  
  367. //
  368. // Return memory to the free pool.
  369. // Currently this does not return the physical pages associated with the
  370. // memory, but it should.
  371. // 
  372. void
  373. BucketAllocator::free( void * cp )
  374. {   
  375.     int bucket;
  376.     union overhead *op;
  377.     
  378.     Debug( "BucketAllocator::free( %x )\n", cp );
  379.     if( cp == 0 )
  380.     return;
  381.     op = (union overhead *) ( (char *) cp - sizeof( union overhead ) );
  382.  
  383.     assert( op->ov_magic == MAGIC );    // make sure it was in use
  384.     assert( op->ov_rmagic == RMAGIC );
  385.  
  386.     if( op->ov_index <= 13 )
  387.     assert( *(unsigned int *)((char *)op + op->ov_size + 1 - RSLOP) == RMAGIC );
  388.  
  389.     assert( op->ov_index < NumberOfBuckets );
  390.     bucket = op->ov_index;
  391.     bucketLock[bucket].reserve();
  392.     op->ov_next = nextf[ bucket ];
  393.     nextf[ bucket ] = op;
  394.     bucketLock[bucket].release();
  395. }
  396.  
  397. #ifdef __GNUG__
  398. extern "C" void *malloc( unsigned size)
  399. #else
  400. void *malloc( unsigned size)
  401. #endif
  402. {
  403.     return( ( void * )HardwareMemoryAllocator.allocate( size ) );
  404. }
  405.  
  406. #ifdef __GNUG__
  407. extern "C" void free(void * ptr)
  408. #else
  409. void free(void * ptr)
  410. #endif
  411. {
  412.     HardwareMemoryAllocator.free( (void *) ptr );
  413. }
  414.